package chapter9;

import java.util.Random;

/**
 * 中位数和顺序统计量-期望为线性的选择算法
 */
public class RandomizedSelect {

    /**
     * 以快排为基础,同时选择第i小的数
     *
     * @param A
     * @param p
     * @param r
     * @param i
     * @return
     */
    public static int randomizedSelect(int[] A, int p, int r, int i) {
        if (p == r) {
            return A[p];
        }
        int q = randomizedPartition(A, p, r);
        // 排完序的基数在第K位,如果与i相同则直接返回
        int k = q - p + 1;
        if (i == k) {
            return A[q];
        } else if (i < k) {
            // 如果i<k,则证明i位于0-k则仍然找此区间找第i个数
            return randomizedSelect(A, p, q - 1, i);
        } else {
            // 如果i>k,则认为i位于k-n之间,那么在此区间的位置就是第i-k位置
            return randomizedSelect(A, q + 1, r, i - k);
        }
    }

    private static int randomizedPartition(int[] A, int p, int r) {
        Random random = new Random();
        int i = random.nextInt(r - p + 1) + p;

        int temp = A[i];
        A[i] = A[r];
        A[r] = temp;

        return partition(A, p, r);
    }

    private static int partition(int[] A, int p, int r) {
        int x = A[r];
        int i = p - 1;
        for (int j = p; j <= r - 1; j++) {
            if (A[j] < x) {
                i++;
                swap(A, i, j);
            }
        }
        swap(A, i + 1, r);
        return i + 1;
    }

    private static void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

}
